/*  slfbspr.cpp  by K.Tsuru  */
// function ID 2011   DRADIX    since ver 2.181
#ifndef SN_H
#include "sn.h"
#endif
// for sorting
static int sortBySize(const void *e1, const void *e2) {
    return (int)((const SLong *)e2)->DFigures() - (int)((const SLong *)e1)->DFigures();
}
/**************************************************************************
product such as
a[0]a[1]...a[n-1] <-- sorted
is evaluated
origin (a[0]a[n-1])(a[1]a[n-2])...a[n/2]a[n/2-1] (n even) or a[n/2] (n odd)
new        a[0]        a[1]    ...    a[n/2]
At second step each elements has the same figures which is efficient for
 FFT multiplication.
**************************************************************************/
SLong BothSideProduct(const SNBlock <SLong>& a, const uint N, bool sort) {
    if(N == 1) return a(0);

    SLong* r = new SLong[N];

    for(uint i = 0; i < N ; i++) r[i] = a(i);
    if (sort) qsort(r, N, sizeof(SLong), sortBySize);   // sort into r[0] >= r[1] >= ...
    uint n = N;
    while(n > 1) {
        if (sort) qsort(r, n, sizeof(SLong), sortBySize);   // does not so speed up
        bool odd = n & 1;
        uint j;
        if(odd) {
            for(j = 0; j < n/2; j++) r[j] = r[j]*r[n-j-1];
        //  r[j] == r[n/2+1];
            n = n/2 + 1;
        } else {
            for(j = 0; j < n/2; j++) r[j] = r[j]*r[n-j-1];
            n = n/2;
        }
    }
    SLong R(r[0]);
    delete[] r;
    return R;
}